home *** CD-ROM | disk | FTP | other *** search
/ C & C++ Multimedia Cyber Classroom / C and C++ Multimedia Cyber Classroom (Prentice Hall) (1998).iso / src / fig15_11.jar / Ch15 / Fig15_11 / List.h < prev    next >
C/C++ Source or Header  |  1997-11-04  |  4KB  |  166 lines
  1. // Fig. 15.3: list.h
  2. // Template List class definition
  3. #ifndef LIST_H
  4. #define LIST_H
  5.  
  6. #include <iostream.h>
  7. #include <assert.h>
  8. #include "listnd.h"
  9.  
  10. template< class NODETYPE >
  11. class List {
  12. public:
  13.    List();      // constructor
  14.    ~List();     // destructor
  15.    void insertAtFront( const NODETYPE & );
  16.    void insertAtBack( const NODETYPE & );
  17.    bool removeFromFront( NODETYPE & );
  18.    bool removeFromBack( NODETYPE & );
  19.    bool isEmpty() const;
  20.    void print() const;
  21. private:
  22.    ListNode< NODETYPE > *firstPtr;  // pointer to first node
  23.    ListNode< NODETYPE > *lastPtr;   // pointer to last node
  24.  
  25.    // Utility function to allocate a new node
  26.    ListNode< NODETYPE > *getNewNode( const NODETYPE & );
  27. };
  28.  
  29. // Default constructor
  30. template< class NODETYPE >
  31. List< NODETYPE >::List() : firstPtr( 0 ), lastPtr( 0 ) { }
  32.  
  33. // Destructor
  34. template< class NODETYPE >
  35. List< NODETYPE >::~List()
  36. {
  37.    if ( !isEmpty() ) {    // List is not empty
  38.       cout << "Destroying nodes ...\n";
  39.  
  40.       ListNode< NODETYPE > *currentPtr = firstPtr, *tempPtr;
  41.  
  42.       while ( currentPtr != 0 ) {  // delete remaining nodes
  43.          tempPtr = currentPtr;
  44.          cout << tempPtr->data << '\n';
  45.          currentPtr = currentPtr->nextPtr;
  46.          delete tempPtr;
  47.       }
  48.    }
  49.  
  50.    cout << "All nodes destroyed\n\n";
  51. }
  52.  
  53. // Insert a node at the front of the list
  54. template< class NODETYPE >
  55. void List< NODETYPE >::insertAtFront( const NODETYPE &value )
  56. {
  57.    ListNode< NODETYPE > *newPtr = getNewNode( value );
  58.  
  59.    if ( isEmpty() )  // List is empty
  60.       firstPtr = lastPtr = newPtr;
  61.    else {          // List is not empty
  62.       newPtr->nextPtr = firstPtr;
  63.       firstPtr = newPtr;
  64.    }
  65. }
  66.  
  67. // Insert a node at the back of the list
  68. template< class NODETYPE >
  69. void List< NODETYPE >::insertAtBack( const NODETYPE &value )
  70. {
  71.    ListNode< NODETYPE > *newPtr = getNewNode( value );
  72.  
  73.    if ( isEmpty() )  // List is empty
  74.       firstPtr = lastPtr = newPtr;
  75.    else {          // List is not empty
  76.       lastPtr->nextPtr = newPtr;
  77.       lastPtr = newPtr;
  78.    }
  79. }
  80.  
  81. // Delete a node from the front of the list
  82. template< class NODETYPE >
  83. bool List< NODETYPE >::removeFromFront( NODETYPE &value )
  84. {
  85.    if ( isEmpty() )             // List is empty
  86.       return false;             // delete unsuccessful
  87.    else {
  88.       ListNode< NODETYPE > *tempPtr = firstPtr;
  89.  
  90.       if ( firstPtr == lastPtr )
  91.          firstPtr = lastPtr = 0;
  92.       else
  93.          firstPtr = firstPtr->nextPtr;
  94.  
  95.       value = tempPtr->data;  // data being removed
  96.       delete tempPtr;
  97.       return true;            // delete successful
  98.    }
  99. }
  100.  
  101. // Delete a node from the back of the list
  102. template< class NODETYPE >
  103. bool List< NODETYPE >::removeFromBack( NODETYPE &value )
  104. {
  105.    if ( isEmpty() )
  106.       return false;   // delete unsuccessful
  107.    else {
  108.       ListNode< NODETYPE > *tempPtr = lastPtr;
  109.  
  110.       if ( firstPtr == lastPtr )
  111.          firstPtr = lastPtr = 0;
  112.       else {
  113.          ListNode< NODETYPE > *currentPtr = firstPtr;
  114.  
  115.          while ( currentPtr->nextPtr != lastPtr )
  116.             currentPtr = currentPtr->nextPtr;
  117.  
  118.          lastPtr = currentPtr;
  119.          currentPtr->nextPtr = 0;
  120.       }
  121.  
  122.       value = tempPtr->data;
  123.       delete tempPtr;
  124.       return true;   // delete successful
  125.    }
  126. }
  127.  
  128. // Is the List empty?
  129. template< class NODETYPE > 
  130. bool List< NODETYPE >::isEmpty() const 
  131.    { return firstPtr == 0; }
  132.  
  133. // Return a pointer to a newly allocated node
  134. template< class NODETYPE >
  135. ListNode< NODETYPE > *List< NODETYPE >::getNewNode( 
  136.                                         const NODETYPE &value )
  137. {
  138.    ListNode< NODETYPE > *ptr = 
  139.       new ListNode< NODETYPE >( value );
  140.    assert( ptr != 0 );
  141.    return ptr;
  142. }
  143.  
  144. // Display the contents of the List
  145. template< class NODETYPE >
  146. void List< NODETYPE >::print() const
  147. {
  148.    if ( isEmpty() ) {
  149.       cout << "The list is empty\n\n";
  150.       return;
  151.    }
  152.  
  153.    ListNode< NODETYPE > *currentPtr = firstPtr;
  154.  
  155.    cout << "The list is: ";
  156.  
  157.    while ( currentPtr != 0 ) {
  158.       cout << currentPtr->data << ' ';
  159.       currentPtr = currentPtr->nextPtr;
  160.    }
  161.  
  162.    cout << "\n\n";
  163. }
  164.  
  165. #endif
  166.